/**
 * TestApple.java created by zhangzhidong 
 * at 下午7:37:28 2016年9月12日
 */
package algorithm;

/**
 * @author zhangzhidong<br>
 * comment generated at 2016年9月12日下午7:37:28<br>
 * 一种苹果包装只有6个装和8个装，输入一个想买的苹果数目，返回所需要买的最小的袋数
 * 假如输入20，返回 3 2袋6 1 袋8 共3袋
 * 如果不能正好购买返回-1
 */
public class TestApple {

	/**
	 * 方案数
	 * 下午7:37:28 2016年9月12日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int res = get(100);
		System.out.println(res);
	}
	public static int get(int k ){
		return value(0,k,0);
	}
	public static int value(int cur,int exp,int num){
		if(cur + 6 ==  exp || cur + 8 == exp ){
			return 1 + num;
		}
		if(cur < exp){
			int a = value(cur+6,exp,num+1);
			int b = value(cur+8,exp,num+1);
			return Math.min(a == -1 ? b:a, b == -1? a:b);
		}else{
			return  -1;
		}
	}
	
	//方案数
//	public static int get(int k ){
//		return value(0,k);
//	}
//	public static int value(int cur,int exp){
//		if(cur == exp){
//			return 1;
//		}
//		if(cur < exp){
//			int a = value(cur+6,exp);
//			int b = value(cur+8,exp);
//			return (a == -1?0:a)+ (b==-1?0:b);
//		}else{
//			return -1;
//		}
//	}

}
